1. Field of the Invention
The present invention relates generally to a computer system, and more particularly to a method of reducing code size of a program by controlling the control flow of the program using software in a computer system including a microprocessor and a memory.
2. Description of the Related Art
Portable devices or small-sized electronic appliances used in the office or at home, such as refrigerators, cleaners, printers or flash memory cards, are equipped with middleware that cooperates with a real time operating system in order to control devices installed in the electronic appliances, such as motors, in real time. Since electronic appliances are mass-produced in a range of several millions to several billions per year, it is very important to reduce the manufacturing cost of the electronic appliances. A computer system that is installed in the electronic appliance in order to control the operation of the electronic appliance in real time may include a processor, a memory and a peripheral input/output device. Among the above components of the computer system, the memory, such as SRAM or DRAM, generally requires a relatively higher manufacturing cost. Therefore, it is necessary to reduce the size of a program in order to reduce the manufacturing cost of the memory.
If the size of the program is reduced, the manufacturing cost of the memory will also be reduced. This kind of gain may be realized when fabricating memory chips, which are provided with a predetermined size corresponding to a multiple of 2, such as 256 KB, 1 MB, and 2 MB. For instance, when it is necessary to use a 2 MB memory chip for a program having a size of 1.2 MB, if it is possible to reduce the size of the program to a size less than or equal to 1 MB, a system can be established by using a 1 MB memory chip. If the size of the memory chip is reduced, the amount of power required for driving the memory can be reduced. In addition, if the size of the program is reduced, it is possible to operate the memory at a lower power even if the size of the memory chip is not reduced, so that power consumption can be reduced. Such a characteristic of the low-power operation is especially advantageous when it is applied to mobile electronic appliances.
In this regard, various conventional technologies have been suggested in order to minimize the size of various code. For example, a compression technique has been suggested, which formats the program such that direct execution of the program is impossible, and a compaction technique, which formats the program in the form of an executable program. The compression technique is classified into a hardware compression technique using a hardware compressor and a hardware restorer, and a software compression technique in which compression and restoration are executed through software via a CPU.
The hardware compression technique can be implemented through various schemes. For instance, according to the hardware compression technique, data is compressed and stored in a main memory based on a line unit of an internal cache, and then the compressed data are released by a hardware restorer when a corresponding compression cache line is accessed, thereby storing the released data in the internal cache. However, although the hardware compression technique can reduce the time required for data restoration, the manufacturing cost may be increased because it requires the hardware restorer, so the hardware compression technique may not be suitable for a computer system, which is installed in the electronic appliance in order to control the operation of the electronic appliance in real time.
According to the software compression technique, the main memory is divided into a compression area and a non-compression area, and these areas are managed by the operating system. In detail, a memory manager of the operating system directly restores data, and stores the restored data in the non-compression area if the data requires a specific address or the data has a higher probability of use. At this time, if the size of the non-compression area is insufficient, some data stored in the non-compression area with a lower probability of use is compressed and then stored in the compression area. However, although the software compression technique does not require additional hardware, such as a compressor, a relatively long time is necessary to compress and restore the data because the software compression technique is slower than the hardware compressor. In addition, the existing operating system must be modified. Therefore, both the software compression technique and the hardware compression technique may not be suitable for the computer system embedded in the electronic appliance.
Compaction techniques can be classified into ISA (instruction set architecture) modification schemes, and a program modification schemes for modifying a program by using instructions. According to the ISA modification scheme, instruction sets having different sizes, such as THUMB® (16 bits) and ARM (32 bits) and MIPS 16 (16 bits) and MIPS14 (14 bits), are defined so as to use the instruction sets according to applications. However, the ISA modification scheme requires a mass-storage processor, such as ARM or MIPS, and such a mass-storage processor is not suitable for some applications. The acronym “ARM” refers to “advanced RISC machine,” where the acronym “RISC” refers to “reduced instruction set computing.” The acronym “MIPS” refers to “microprocessor without interlocked pipeline stages.”
In addition, according to the program modification scheme, which has been variously studied in the past five years, the same or similar instructions in the program are combined into one instruction set, and a branch to newly constructed areas is performed at all locations where the instruction set exists. In detail, the program modification scheme is based on procedural abstraction (PA) and cross jumping (CJ)/tail merging. According to PA, if there are N instructions, which are similar or identical to each other, they are decomposed into one function, and a function call instruction is substituted for the N instructions. In particular, in CJ, if the last instruction of the instructions branches to the same location, the instructions are shifted into the start position of the branch point.
In a case of an actual program, the order of the instructions may be changed or the register name may be partially incorrect. In this case, instruction reordering and register renaming schemes are utilized in order to replace similar instructions with the same instructions. According to the test result, if the above schemes are applied at compile time, the code size can be reduced by 5% on average compared to its original size. In addition, if the above schemes are applied to a binary file after linking, the code size can be reduced by 30% on average compared to its original size. Since the binary file has all information related to the control flow of the program, the code size can be effectively optimized.
Since the iterative instructions are decomposed into the function, the program modification scheme must use additional instructions in order to call and execute the function. In detail, a current return address must be stored in a stack when calling the function, and registers of the called function must be protected in the stack. In addition, the control flow of the program must return to the original stage after the function has been executed. For this reason, an instruction “Sequential Echo <offset>,<length>” has been suggested in order to reduce the use of the additional instructions.
The instruction “Sequential Echo <offset>,<length>” refers to executing a predetermined number (<length>) of instructions from the <offset> position. If this instruction is used, the control flow of the program can return to the original stage after executing corresponding instructions. This can be implemented by modifying the ISA of the processor, the interpreter or the virtual machine, such as the Java Virtual Machine. In addition, an instruction “Bitmask Echo <offset>,<bitmask>” refers to executing the instructions from the <offset> position only when bits corresponding to the instructions are set to “1” in the “bitmask” of the instructions. Therefore, even if there are some different instructions among all the instructions, they may share the code of the program so that the size of the program can be significantly reduced. According to the performance evaluation result, when the above scheme is utilized together with the conventional code optimization technique, the code size can be halved as compared with the conventional code compression technique.
Although the size of the program can be reduced using the Echo instructions, it is necessary to modify the ISA of the microprocessor, in practice. This may require a change of hardware, causing an increase in the development cost of the microcomputer system equipped in the electronic appliance. Accordingly, it is necessary to develop a method of supporting the instructions “Sequential Echo” and “Bitmask Echo” without changing the hardware.